package HW.hw3;

/**************************************************************
* Class DropOutStack
* @author Jeff Thomas - Thomas007
* @vesion 1.0.0
* Date: 03.07.2008
* Copyright 2008, Jeff Thomas
***************************************************************/

import java.util.EmptyStackException;

/**************************************************************
* DropOutStack
* Original code from Section 5.3, Koffman & Wolfgang
* Modified by Jeff Thomas
***************************************************************/
public class DropOutStack<E> implements StackInt<E>
{
/**************************************************************
* Node
* Original code from Section 4.4, Koffman & Wolfgang
* Modified into a Double Linked List, Jeff Thomas
***************************************************************/
	public static class Node<E>
	{
		private E data;
		private Node<E> next = null;
		private Node<E> prev = null;
/**************************************************************
* Node
* @param dataItem - Generic variable for the data of the Node
* Task:	1. Assign data to parameter
* Side Effects: None
***************************************************************/		
		private Node(E dataItem)
		{
			data = dataItem;
			next = null;
			prev = null;
		}
/**************************************************************
* Node
* @param dataItem - Generic variable for the data of the Node
* @param nodeRef - Reference to the next node
* Task:	1. Assign data to parameter
*			2. Assign next to the nodeRef
* Side Effects: None
***************************************************************/		
		private Node(E dataItem, Node<E> nodeRef)
		{
			data = dataItem;
			next = nodeRef;
			prev = null;
		}
	}
	
	private Node<E> topOfStackRef = null;
	private Node<E> bottomOfStackRef = null;
	private int size = 0;
	final int MAX_SIZE = 5;
/**************************************************************
* Push
* @return - A reference to the objected pushed on the stack
* Task:	1. If our stack has reached the max size, remove the
*			bottom node
*			2. If our stack is empty, create a new node and setup
*			references to bottom and top, increment size
*			3. Else insert our node perfor the previous, increment
*			size
* Side Effects: None
***************************************************************/	
	public E push(E obj)
	{
		if (size >= MAX_SIZE)
		{
			size--;
			bottomOfStackRef.prev.next = null;
			bottomOfStackRef = bottomOfStackRef.prev;
		}
		if (topOfStackRef == null)
		{
			size++;
			topOfStackRef = new Node<E>(obj);
			bottomOfStackRef = topOfStackRef;
		}
		else 
		{
			size++;
			topOfStackRef = new Node<E>(obj, topOfStackRef);
			topOfStackRef.next.prev = topOfStackRef;
		}
		return obj;
	}
/**************************************************************
* Pop
* @return - Reference to the object removed from the stack
* Task:	1. If the stack is empty, throw EmptyStackException
*			2. Move topOfStackRef to next node, return Node ref
*			3. Decrement size
* Side Effects: None
***************************************************************/	
	public E pop()
	{
		if (empty())
			throw new EmptyStackException();
		else
		{
			size--;
			E result = topOfStackRef.data;
			topOfStackRef = topOfStackRef.next;
			return result;
		}
	}
/**************************************************************
* Peek
* @return - Reference to the object removed from the stack
* Task:	1. If the stack is empty, throw EmptyStackException
*			2. return the data from the Top of the Stack
* Side Effects: None
***************************************************************/	
	public E peek()
	{
		if (empty())
			throw new EmptyStackException();
		else
			return topOfStackRef.data;
	}
/**************************************************************
* Empty
* @return - String of colors seperated by "\n" new line
* Task:	1. Add each color from the stack to a StringBuilder
*			2. Seperate each color with a "\n"
* Side Effects: None
***************************************************************/	
	public boolean empty()
	{
		return topOfStackRef == null;
	}
/**************************************************************
* To String
* @return - String of nodes in the stack
* Task:	1. Add each node from the stack to a StringBuilder
*			2. Seperate each color with a "==>"
*			3. Stack is displayed top to bottom from left to right
* Side Effects: None
* Code taken from Section 4.4, Koffman & Wolfgang
***************************************************************/	
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		Node<E> nodeRef = topOfStackRef;
		while (nodeRef != null) 
		{
			sb.append(nodeRef.data);
			if (nodeRef.next != null)
				sb.append(" ==> ");
			nodeRef = nodeRef.next;
		}
		return sb.toString();
	}
}
/**************************************************************
* I, Jeff Thomas, certify that each part of this program was
* written by me, except as noted within the code.
*
*						_________________________
***************************************************************/